#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
constexpr int MAXV = 100, INF = 1 << 30;
int pre[MAXV], d[MAXV];
bool used[MAXV];
int cost[MAXV][MAXV];
int V;

void dijkstra(int s) {
    fill(d, d + V, INF);
    fill(used, used + V, false);
    fill(pre, pre + V, -1);
    d[s] = 0;
    while (true) {
        int v = -1;
        for (int u = 0; u < V; u++) 
            if (!used[u] && (v == -1 || d[v] > d[u])) v = u;
        if (v == -1) break;
        used[v] = true;
        for (int i = 0; i < V; i++) {
            if (d[i] > d[v] + cost[v][i]) {
                pre[i] = v;
                d[i] = d[v] + cost[v][i];
            }
        }
    }
}

vector<int> get_path(int t) {
    vector<int> path;
    for (; t != -1; t = pre[t]) path.push_back(t);
    reverse(path.begin(), path.end());
    return path;
}